package com.nanbei.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @ClassDescription: 广度优先算法
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/1 15:54
 */
public class BFS {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        v1.setEdges(Arrays.asList(new Edge(v3), new Edge(v2), new Edge(v6)));
        v2.setEdges(Arrays.asList(new Edge(v4)));
        v3.setEdges(Arrays.asList(new Edge(v4), new Edge(v6)));
        v4.setEdges(Arrays.asList(new Edge(v5)));
        v5.setEdges(Arrays.asList());
        v6.setEdges(Arrays.asList(new Edge(v5)));


        bfs(v1);
    }

    // 广度优先算法
    private static void bfs(Vertex v) {
        LinkedList<Vertex> verticesQueue = new LinkedList<>();
        v.setVisited(true);
        verticesQueue.offer(v);
        while (!verticesQueue.isEmpty()) {
            Vertex poll = verticesQueue.poll();
            System.out.println(poll.getName());
            List<Edge> edges = poll.getEdges();
            for (Edge edge : edges) {
                Vertex vertex = edge.getLinked();
                if (!vertex.isVisited()){
                    vertex.setVisited(true);
                    verticesQueue.offer(vertex);
                }
            }
        }
    }
}
